package com.matrix.dungeon;



public class Generate{
	static final int MIN_ROOM_WIDE = 4;
	static final int MAX_ROOM_WIDE = 9;
	static final int MIN_ROOM_HIGH = 4;
	static final int MAX_ROOM_HIGH = 9;
	
	public static final int SYM_VOID = 0;
	public static final int SYM_ROOM = 1;
	public static final int SYM_WALL = 2;
	public static final int SYM_TUNN = 3;
	public static final int SYM_CORN = 4;
	
	
	Dungeon dungeon = new Dungeon();
	
	class Dungeon{
		int wide = 31;
		int high = 33;
		Cell[][] cellData = new Cell[high][wide];
		int minRooms;
		int maxRooms = 16;
		Room[] rooms = new Room[maxRooms];
		int roomsCount = 0;
		
		public Dungeon(){
			for(int i = 0;i < wide;i++)
				for(int j = 0;j < high;j++)
					cellData[j][i] = new Cell(i, j);
		}
	}
	
	class Cell{
		//coordination, unique id
		int x;
		int y;
		//cell type in the map
		int type = SYM_VOID;
		//wall have max 2 rooms and corner have max 4 rooms
		int[] relatedRooms = new int[4];
		int relatedRoomsCount = 0;
		
		public Cell(int pX, int pY){
			for(int i = 0;i < 4;i++){
				relatedRooms[i] = -1;
			}
		}
		
		public void setType(int pType){
			type = pType;
		}
		
		public void setRoom(int pRoomId){
			if(relatedRoomsCount < 4){
				for(int i = 0;i < 4;i++){
					if(relatedRooms[i] == pRoomId){
						System.out.print("Duplicated room " + pRoomId + "\n");
						return;
					}else{
						if(relatedRooms[i] == -1){
							relatedRooms[i] = pRoomId;
							relatedRoomsCount++;
							return;
						}
					}
				}
			}else{
				throw new RuntimeException("relatedRooms more than 4");
			}
		}
		
		public boolean isRelatedRoom(int pRoomId){
			for(int i = 0;i < 4;i++){
				if(relatedRooms[i] == pRoomId){
					return true;
				}
			}
			return false;
		}
		
		public boolean hasUncoRelatedRoom(Array pUncoRooms){
			for(int i = 0;i < 4;i++){
				if(relatedRooms[i] == -1){
					continue;
				}else{
					if(pUncoRooms.isContain(relatedRooms[i]) != -1)return true;
				}
			}
			return false;
		}
	}
	
	class Room{
		int id;
		int wide;
		int high;
		int[] center = new int[2];
		int[] startLT = new int[2];
		
		public Room(int pId, int pWide, int pHigh, int[] pCenter, int[] pStartLT){
			id = pId;
			wide = pWide;
			high = pHigh;
			center = pCenter;
			startLT = pStartLT;
		}
	}

	class NodeMap{
		Node[][] nodes;
		int numOfItem = 0;
		
		public NodeMap(int pWide, int pHigh){
			nodes = new Node[pWide][pHigh];
		}
		
		public void add(Node pNode){
			if(getNode(pNode.x, pNode.y) != null){
				int i = 0;
				i+=1;
				int j = i;
			}
			nodes[pNode.x][pNode.y] = pNode;
			numOfItem++;
		}
		
		public Node getNode(int pX, int pY){
			return nodes[pX][pY];
		}
	}

	//for path finding 
	class Node{
		int x;
		int y;
		//A* use G(start to current) and H(estimated current to end)
		//I only use current to end H
		int value;
		int parentX;
		int parentY;
		
		public Node(int pX, int pY, int pValue, int pParentX, int pParentY){
			x = pX;
			y = pY;
			value = pValue;
			parentX = pParentX;
			parentY = pParentY;
		}
		
		@Override
		public boolean equals(Object obj) {
			return x == ((Node)obj).x && y == ((Node)obj).y;
		}
	}

	
	void generateRooms(){
		for(int i = 0; i < dungeon.maxRooms; i++){
			Room room = generateRoom(i);
			if(room != null){
				
				dungeon.rooms[dungeon.roomsCount] = room;
				
				//set node data
				for(int j = 0;j < room.wide;j++)
					for(int k = 0;k < room.high;k++){
						if(j == 0 || j == (room.wide-1) || k == 0 || k == (room.high - 1)){
							if((j == 0 && k == 0) 
									|| (j == room.wide - 1 && k == 0)
									|| (j == 0 && k == room.high - 1)
									|| (j == room.wide - 1 && k == room.high - 1)){
								dungeon.cellData[room.startLT[1]+k][room.startLT[0]+j].setType(SYM_CORN);
							}else{
								dungeon.cellData[room.startLT[1]+k][room.startLT[0]+j].setType(SYM_WALL);
							}	
						}else{
							dungeon.cellData[room.startLT[1]+k][room.startLT[0]+j].setType(SYM_ROOM);
						}
						dungeon.cellData[room.startLT[1]+k][room.startLT[0]+j].setRoom(dungeon.roomsCount);
					}
				dungeon.roomsCount++;
			}
		}
	}
	
	Room generateRoom(int pId){
		System.out.print("generateRoom\n");
		int[] newCenter = new int[2];
		int[] startLT = new int[2];
		int newWide = 0;
		int newHigh = 0;
		int i;
		for(i = 0; i < 25; i++){
			newWide = randomInt(MIN_ROOM_WIDE, MAX_ROOM_WIDE);
			newHigh = randomInt(MIN_ROOM_HIGH, MAX_ROOM_HIGH);
			
			if(newWide % 2 == 0){
				newCenter[0] = randomInt(1 + newWide/2, dungeon.wide - 1 - newWide/2);
				newCenter[1] = randomInt(1 + newHigh/2, dungeon.high - 1 - newHigh/2);
				
				startLT[0] = newCenter[0] - newWide/2;
				startLT[1] = newCenter[1] - newHigh/2;
			}else{
				newCenter[0] = randomInt(1 + (newWide - 1)/2, dungeon.wide - 1 - (newWide - 1)/2 - 1);
				newCenter[1] = randomInt(1 + (newHigh - 1)/2, dungeon.high - 1 - (newHigh - 1)/2 - 1) ;
				
				startLT[0] = newCenter[0] - (newWide - 1)/2;
				startLT[1] = newCenter[1] - (newHigh - 1)/2;
			}
			
			System.out.print("i "+i+" center " + newCenter[0]+","+newCenter[1]+" w,h " + newWide+","+newHigh+"\n");
			
			if(!validateSpace(startLT, newWide, newHigh))break;
		}
		
		if(i >= 25){
			return null;
		}else{
			return new Room(pId, 
					newWide,
					newHigh, 
					newCenter,
					startLT);
		}
	}
	
	void generateTunnels(){
		if(dungeon.roomsCount <= 1)return;
		
		int roomsCount = dungeon.roomsCount;
		Array uncoRooms = new Array(roomsCount);
		Array connRooms = new Array(roomsCount);

		for(int i = 0;i < roomsCount;i++){
			uncoRooms.add(i);
		}
		
		while(uncoRooms.numOfItem > 0){
			int[] start;
			int[] end;
			int startRoom;
			int endRoom;
			
			if(connRooms.numOfItem == 0){
				startRoom = uncoRooms.items[0];
				endRoom = uncoRooms.items[1];
				start = dungeon.rooms[startRoom].center;
				end = dungeon.rooms[endRoom].center;
				
			}else{
				startRoom = uncoRooms.items[randomInt(0, uncoRooms.numOfItem - 1)];
				endRoom = connRooms.items[randomInt(0, connRooms.numOfItem - 1)];
				start = dungeon.rooms[startRoom].center;
				end = dungeon.rooms[endRoom].center;
			}			
			generateTunnel(start, end, startRoom, endRoom, uncoRooms, connRooms);
		}
	}
	
	int distance(int[] pStart, int[] pEnd){
		return Math.abs(pStart[1] - pEnd[1]) + Math.abs(pStart[0] - pEnd[0]);
	}
	
	boolean generateTunnel(int[] pStart, int[] pEnd, int pStartRoom, int pEndRoom, Array pUncoRooms, Array pConnRooms){
		System.out.print("Generate one tunnel\n");
		
		if(pStart[0] == pEnd[0] && pStart[1] == pEnd[1]){
			throw new RuntimeException("start and end is same\n");
		}
		
		NodeMap close = new NodeMap(dungeon.wide, dungeon.high);
		Heap open = new Heap(dungeon.wide * dungeon.high);
		
		//add first 4 open node
		addOpenNode(pStart, open, close, pStart, pEnd);
		
		//add start node to close map
		close.add(new Node(pStart[0], pStart[1], 0, -1, -1));
		
		while(!open.isEmpty()){
			Node curNode = open.getTop();
			close.add(curNode);
			open.del();
			addOpenNode(new int[]{curNode.x, curNode.y}, open, close, pStart, pEnd);
			
			//drawDungeon(open, close);
			
			if(curNode.x == pEnd[0] && curNode.y == pEnd[1]){
				if(pUncoRooms.isContain(pStartRoom) != -1){
					pUncoRooms.del(pStartRoom);
					pConnRooms.add(pStartRoom);
				}
				
				if(pUncoRooms.isContain(pEndRoom) != -1){
					pUncoRooms.del(pEndRoom);
					pConnRooms.add(pEndRoom);
				}
				break;
			}else if(dungeon.cellData[curNode.y][curNode.x].type == SYM_WALL){
				Cell curCell = dungeon.cellData[curNode.y][curNode.x];
				
				if(curCell.relatedRoomsCount == 1 && curCell.isRelatedRoom(pStartRoom))continue;
				
				if(curCell.relatedRoomsCount > 1 && curCell.hasUncoRelatedRoom(pConnRooms)){
					for(int i = 0;i < 4;i++){
						System.out.print("related rooms " + dungeon.cellData[curNode.y][curNode.x].relatedRooms[i] + " ");
					}
					System.out.print("\n");
					pEnd[0] = curNode.x;
					pEnd[1] = curNode.y;
					if(pUncoRooms.isContain(pStartRoom) != -1){
						pUncoRooms.del(pStartRoom);
						pConnRooms.add(pStartRoom);
					}
					for(int i = 0;i < 4;i++){
						if(curCell.relatedRooms[i] == -1)break;
						else {
							if(pUncoRooms.isContain(curCell.relatedRooms[i]) != -1){
								pUncoRooms.del(curCell.relatedRooms[i]);
								pConnRooms.add(curCell.relatedRooms[i]);
							}
						}
					}
					break;
				}			
				
			}
		}
		
		if(open.isEmpty()){
			return false;
		}else{
			int tX = pEnd[0], tY = pEnd[1];
			while(true){
				if(dungeon.cellData[tY][tX].type != SYM_ROOM)
					dungeon.cellData[tY][tX].setType(SYM_TUNN);
				
				int paX = close.getNode(tX, tY).parentX;
				int paY = close.getNode(tX, tY).parentY;
				tX = paX;
				tY = paY;
				
				if(tX == pStart[0] && tY == pStart[1])break;
			}
			return true;
		}
	}
	
	void addOpenNode(int[] pCenterCoord, Heap pOpen, NodeMap pClose, int[] pStart, int[] pEnd){
		System.out.print("addOpenNode\n");
		// tunnel only can build in 4 direction, so we only consider 4 nodes
		for(int i = pCenterCoord[0] - 1,n = pCenterCoord[0] + 1;i <= n;i++){
			if(i < 0 || i >= dungeon.wide)continue;
			
			for(int j = pCenterCoord[1] - 1, m = pCenterCoord[1] + 1;j <= m;j++){
				//System.out.print("j="+j+" 2nd="+)
				if(j < 0 || j >= dungeon.high
						|| (i == pCenterCoord[0] && j == pCenterCoord[1])
						|| (Math.abs(pCenterCoord[0] - i) + Math.abs(pCenterCoord[1] - j)) > 1
						//|| (dungeon.cellData[j][i] == SYM_WALL && )
						//|| dungeon.cellData[j][i] != SYM_VOID
						|| dungeon.cellData[j][i].type == SYM_CORN
						|| pClose.getNode(i, j) != null)continue;
				
				int[] cur = new int[]{i, j};
				if(pOpen.isContain(i, j) != -1){
					if((distance(pStart, pCenterCoord) + 1) < distance(pStart, cur)){
						pOpen.setItem(i, j, new Node(i, j, distance(pStart, pCenterCoord) + 1 + distance(pEnd, cur), pCenterCoord[0], pCenterCoord[1]));
					}
				}else{
					System.out.print("center node " + pCenterCoord[0]+","+pCenterCoord[1]+" new open node " + i+","+j+'\n');
					pOpen.add(new Node(i, j,
							distance(pEnd, cur),//distance(pStart, cur) + distance(pEnd, cur),
							pCenterCoord[0], pCenterCoord[1]));
				}
			}
		}
	}
	
	boolean validateSpace(int[] pStartLT, int pWide, int pHigh){
		//System.out.print("startLT = " + pStartLT[0] + "," + pStartLT[1] + " wide = " + pWide + " high = " + pHigh + '\n');
		//check overlap
		for(int i = 0; i < pHigh; i++)
			for(int j = 0; j < pWide; j++){
				if(dungeon.cellData[pStartLT[1] + i][pStartLT[0] + j].type != SYM_VOID){
					return true;
				}
			}
		return false;
	}
	
	//return [min,max]
	int randomInt(int pMin, int pMax){
		return pMin + (int)(Math.random() * (pMax - pMin));
	}
	
	void drawDungeon(Heap pOpen, NodeMap pClose){
		for(int i = 0;i < dungeon.high;i++){
			for(int j = 0;j<dungeon.wide;j++){
				if(pOpen.isContain(j, i) != -1){
					System.out.print("o");
				}else if(pClose.getNode(j, i) != null){
					System.out.print("c");
				}else{
					if(dungeon.cellData[i][j].type == SYM_VOID)
						System.out.print("*");
					else if(dungeon.cellData[i][j].type == SYM_WALL)
						System.out.print("#");
					else if(dungeon.cellData[i][j].type == SYM_TUNN)
						System.out.print("0");
					else if(dungeon.cellData[i][j].type == SYM_CORN)
						System.out.print("+");
					else System.out.print("-");
				}
				
				if(j == (dungeon.wide-1))
					System.out.print('\n');
			}
		}
	}
	
	void drawDungeon(){
		for(int i = 0;i < dungeon.high;i++)
			for(int j = 0;j < dungeon.wide;j++){
				if(dungeon.cellData[i][j].type == SYM_VOID)
					System.out.print("*");
				else if(dungeon.cellData[i][j].type == SYM_WALL)
					System.out.print("#");
				else if(dungeon.cellData[i][j].type == SYM_TUNN)
					System.out.print("0");
				else if(dungeon.cellData[i][j].type == SYM_CORN)
					System.out.print("+");
				else System.out.print("-");
				
				if(j == (dungeon.wide-1))
					System.out.print('\n');
			}
		
		/*for(int i = 0;i < dungeon.maxRooms;i++){
			System.out.print(dungeon.rooms[i].center[1]);
			System.out.print(",");
			System.out.print(dungeon.rooms[i].center[0]);
			System.out.print(" ");
			System.out.print(dungeon.rooms[i].wide);
			System.out.print(" ");
			System.out.print(dungeon.rooms[i].high);
			System.out.print('\n');
		}*/
	}
	
	public int[][][] generate(){
		generateRooms();
		generateTunnels();
		
		//one layer map for test
		int[][][] toplogy = new int[1][dungeon.high][dungeon.wide];
		
		for(int i = 0;i < dungeon.high;i++)
			for(int j = 0;j < dungeon.wide;j++){
				toplogy[0][i][j] = dungeon.cellData[i][j].type;
			}
		return toplogy;
	}
	
	/*
	public static void main(String[] argv){
		Generate generator = new Generate();
		generator.generateRooms();
		generator.drawDungeon();
		generator.generateTunnels();
		generator.drawDungeon();
	}*/
}